package zuosheng.Binarytree;

/**
 * @author lj
 * @Description: 莫瑞斯改写前中后序遍历
 * @date 2020-11-21 11:07
 * @QQ 851477108
 */


public class MorrisBL {

    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int data){
            this.value = data;
        }
    }

    //前序遍历,中左右
    public void morrisPre(Node head){
        if (head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;

        while (cur != null){
            mostRight = cur.left;
            if (mostRight != null){
                while (mostRight != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null){
                    mostRight.right = cur;
                    //cur有左子树,第一次来到左子树的最右节点,它的右子树为空,cur必然也是第一次经过,打印第一次
                    System.out.println(cur.value + " ");
                    cur = cur.left;
                    continue;
                }else {
                    //第二次到达时不打印
                    mostRight.right = null;
                }
            } else {
                //cur无左子树,直接打印cur
                System.out.println(cur.value + " ");
            }
            cur = cur.right;
        }
    }

    //中序遍历,左中右
    public void morrisIn(Node head){
        if (head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;

        while (cur != null){
            mostRight = cur.left;
            if (mostRight != null){
                while (mostRight != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null){
                    //第一次到达不打印
                    //System.out.println(cur.value + " ");
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else {
                    mostRight.right = null;
                }
            }
            //1.无左子树,直接打印
            //2.有左子树,但是第二次到达,第二次的时候打印
            System.out.println(cur.value + " ");
            cur = cur.right;
        }
    }
}
